class Solution {
public:
    using vvi = vector<vector<int>>;
    int ans = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int movingCount(int threshold, int rows, int cols) {
        int i, j;
        if(threshold < 0) return 0;  // 特例情况
        vvi mark(rows, vector<int>(cols, -1));
        backtrack(0, 0, rows, cols, threshold, mark);
        return ans;
    }
    void backtrack(int i, int j, int r, int c, int threshold, vvi& mark) {
        if(i < 0 || i >= r || j < 0 || j >= c || mark[i][j]!=-1) return ;
        if(func(i, j) > threshold) return ;
        mark[i][j] = 1;  // 无需回溯，只是防止重复入队
        ans++;
        int newi, newj;
        for(int k = 0; k < 4; k++) {
            newi = i + dx[k];
            newj = j + dy[k];
            backtrack(newi, newj, r, c, threshold, mark);
        }
    }
    int func(int x, int y) {
        int sum = 0;
        while(x) {
            sum += x%10;
            x /= 10;
        }
        while(y) {
            sum += y%10;
            y /= 10;
        }
        return sum;
    }
};